package leetcode;
/*
   思路：
    1、暴力循环
        记录不重复子串的第一个位置subFirstIndex，子串为[subFirstIndex,i-1],如果当前字符i不和子串内任意一个字符重复，那么依次后移子串。
        如果重复了，取子串的第一个位置为subFirstIndex = 重复位置 + 1；
        时间复杂度：O(n^2)
        空间复杂度：O(1)
    2、滑动窗口
        思考1方法，只有在重复且在子串范围内的时候，才会取上一次重复出现字符的位置+1作为起始字符。那么我们可以记录每个字符出现的位置，如果出现了，直接取位置+1即可。
        可以用Map记录
        时间复杂度：O(n)
        空间复杂度：O(n)
    3、替换2中的map
        map在取值的时候，会进行字符的hash，这个计算过程是很耗时的。我们的计算对象是字符，需要存储信息是位置，可以使用数组的形式来保存具体的信息。
        以字符为index,位置为具体指


 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Code3 {


    public int lengthOfLongestSubstring1(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        //子串第一个字符的位置
        int subFirstIndex = 0;
        int maxLength = 0;
        for (int i = 0; i < s.length(); i++) {
            for(int j = subFirstIndex; j<i; j++){
                if(s.charAt(i) == s.charAt(j)){
                    subFirstIndex = j+1;
                    break;
                }
            }
            int curLength = i - subFirstIndex;
            maxLength = curLength > maxLength ? curLength: maxLength;
        }

        return maxLength;
    }

    public int lengthOfLongestSubstring2(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        //子串第一个字符的位置
        int subFirstIndex = 0;
        int maxLength = 0;
        Map<Character, Integer> lastcharIndex = new HashMap<>(s.length());
        for (int i = 0; i < s.length(); i++) {
            char curChar = s.charAt(i);
            if(lastcharIndex.containsKey(curChar)){
                subFirstIndex = Math.max(subFirstIndex, lastcharIndex.get(curChar) + 1);
            }
            maxLength = Math.max(maxLength, i - subFirstIndex + 1);
            lastcharIndex.put(curChar, i);
        }

        return maxLength;
    }

    public int lengthOfLongestSubstring3(String s) {
        if(s == null || s.length() == 0){
            return 0;
        }
        //子串第一个字符的位置
        int[] charIndexes = new int[256];
        Arrays.fill(charIndexes, 0, 255, -1);
        int maxLength = 0;
        int subFirstIndex = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            subFirstIndex = Math.max(subFirstIndex, charIndexes[s.charAt(i)] + 1);
            maxLength = Math.max(maxLength, i - subFirstIndex + 1);
            charIndexes[s.charAt(i)] = i;
        }

        return maxLength;
    }
}
